/**
 * 动态可调整大小的ArrayList
 * License: BSD
 * Authors: Lucifer (786325481@QQ.com)
 * Copyright: Copyright (C) 2008 Lucifer. All rights reserved.
 */
module system.collections.ArrayList;

import system.Array;
import system.Exception;
import system.collections.IList;
import system.collections.ICollection;
import system.collections.IEnumerable;
import system.collections.IEnumerator;
import system.collections.IComparer;
import system.collections.objectmodel.ReadOnlyListCollection;

/**
 * 表示可通过索引访问的对象的强类型列表。
 * 提供用于对列表进行搜索、排序和操作的方法。
 * Comments:
 *		该类使用大小可按需动态增加的数组实现 IList(T) 泛型接口。
 * 		该类既使用相等比较器又使用排序比较器。
 * 		该类不保证是排序的。
 * 		在执行要求已排序的操作（例如BinarySearch）之前，您必须对其进行排序。
 */
public class ArrayList(T) : IList!(T), ICollection!(T), IEnumerable!(T)
{
    private const int defaultCapacity = 16;
    private T[] theArray;
    private int theSize;
    private int theVersion;

    /**
     * 初始化 ArrayList(T) 类的新实例，该实例为空并且具有指定的初始容量。
     */
    public this()
    {
        this(defaultCapacity);
    }
    /**
     * 初始化ArrayList(T)类的实例，该实例为空并且具有指定的初始容量。
     * Params: capacity = 新列表最初可以存储的元素数。
     * Comments: ArrayList(T) 的容量是 ArrayList(T) 可以容纳的元素数。当向 ArrayList(T) 中添加元素时，将通过重新分配内部数组来根据需要自动增大容量。
     *           如果可以估计集合的大小，那么当指定初始容量后，将无需在向 ArrayList(T) 中添加元素时执行大量的大小调整操作。
     *           可通过调用 trimExcess 方法或通过显式设置 capacity 属性减少容量。减少容量会重新分配内存并复制 ArrayList(T) 中的所有元素。
     *           此构造函数的运算复杂度为 O(n)，其中 n 是 capacity。
     */
    public this(int capacity)
    in
    {
        assert( capacity >= 0 && capacity <= int.max, "Argument capacity is out of range." );
    }
    body
    {
        this.theArray = new T[capacity];
    }
	/**
	 * 初始化 ArrayList(T) 类的新实例，该实例包含从指定集合复制的元素并且具有足够的容量来容纳所复制的元素。
	 * Params: collection = 一个集合，其元素被复制到新列表中。
	 */
    public this(IEnumerable!(T) collection)
    in
    {
        assert( collection !is null, "Argument collection can not be null." );
    }
    body
    {
        ICollection!(T) theCollection = cast(ICollection!(T))collection;
        if( theCollection !is null )
        {
            int count = theCollection.count;
            theArray = new T[count];
            theCollection.toArray(theArray);
            this.theSize = count;
        }
        else
        {
            theArray = new T[defaultCapacity];

            foreach( i; collection )
            {
                this.add(i);
            }
        }
    }

    /**
     * 获取能够容纳的元素总数。
     */
    public final int capacity()
    {
        return this.theArray.length;
    }
    /**
     * 设置能够容纳的元素总数。
     * Throws: ArgumentOutOfRangeException，当 newSize 小于 count 时。
     * Comments: capacity 是 ArrayList(T) 在需要调整大小之前可以存储的元素数，count 则是 ArrayList(T) 中实际存储的元素数。
     *           capacity 总是大于或等于 count。如果在添加元素时 count 超过 capacity，
     *           则通过在复制旧元素和添加新元素之前自动重新分配内部数组来使容量增加。
     *           可通过调用 trimExcess 方法或通过显式设置 capacity 属性减少容量。如果 capacity 的值是显式设置的，
     *           则内部数组也需要重新分配以容纳指定的容量，并且需要复制所有元素。
     */
    public final void capacity(int newSize)
    in
    {
        assert( newSize >= theSize && newSize <= int.max );
    }
    body
    {
        if( newSize != this.theArray.length )
        {
            if( newSize < this.theSize )
            {
                throw new ArgumentOutOfRangeException();
            }
            //因为D语言的数组实现了Copy on Write，
            //所以这里可能会复制内容到新数组，也可能不会。
            theArray.length = newSize;
        }
    }

    /* *************************************************************
     * 实现接口ICollection(T)
     * **************************************************************/

    /**
     * 查看 ArrayList(T) 是否为空。
     */
    public final bool isEmpty()
    {
        return theSize == 0;
    }

    /**
     * 将对象添加到 ArrayList(T) 的结尾处。
     * Params: item = 要添加到 ArrayList(T) 的末尾处的对象。
     *               对于引用类型，该值可以为 null。
     * Comments: ArrayList(T) 接受 null 作为引用类型的有效值并且允许有重复的元素。
     */
    public final bool add(T item)
    {
        //如果我们在数组增长之前查看是否需要增长
        //大概会有25%的性能提升
        if(theSize == theArray.length)
        {
            needGrow(1);
        }
        theArray[theSize++] = item;
        theVersion++;
        return true;
    }

    /* 查看内部数组是否需要进行增长 */
    private void needGrow(int newCount)
    {
        int minSize = this.theSize + newCount;
        if(minSize > this.theArray.length)
        {
            int size = max( max( defaultCapacity, 2 * this.capacity ), minSize );

			assert( size <= int.max );
			assert( size > 0 );

			this.capacity = size;
        }
    }
	/* 比较大小 */
	private int max(int left, int right)
	in
	{
		assert( left >= 0 );
		assert( right >= 0 );
	}
	body
	{
		return left > right ? left : right;
	}

    /**
     * 获取 ArrayList(T) 中实际包含的元素数。
     */
    public final int count()
    {
        return this.theSize;
    }
	/**
	 * 将整个 ArrayList(T) 复制到兼容的一维数组中。
	 * Comments: 由于D数组的切片功能，这里可以指定数组的上下界限。
	 *           此方法使用 Array.copy(T) 复制元素。
	 *           元素按照枚举数循环访问 ArrayList(T) 的顺序复制到 array 中。
	 *           此方法的时间复杂度为O(n)，其中 n 是 count 。
	 */
	public final void toArray(T[] array)
	in
	{
		assert( array !is null );
	}
	body
	{
		Array.copy!(T)(theArray, array, theSize);
	}
	/**
	 * 将一定范围的元素从 ArrayList(T) 复制到兼容的一维数组中。
	 * Params: index = 源 ArrayList(T) 中复制开始位置的从零开始的索引。
	 *         array = 作为从 ArrayList(T) 复制的元素的目标位置的一维数组。
	 * Comments: 由于D数组的切片功能，这里可以指定数组的上下界限。
	 *           此方法使用 Array.copy(T) 复制元素。
	 *           元素按照枚举数循环访问 ArrayList(T) 的顺序复制到 array 中。
	 *           此方法的时间复杂度为O(n)，其中 n 是 count 。
	 */
	public final void toArray(int index, T[] array)
	in
	{
		assert( index >= 0 && index < theSize );
		assert( array !is null );
	}
	body
	{
		Array.copy!(T)(theArray[index..theSize], array, theSize-index);
	}
	/**
	 * 获取一个值，该值指示 ArrayList(T) 是否为只读。
	 */
	public final bool isReadOnly()
	{
		return false;
	}
	/**
	 * 从 ArrayList(T) 中移除所有元素。
	 * Comments: count 被设置为 0，并且对来自该集合的元素的其他对象的引用也被释放。
	 *           capacity 保持不变。若要重置 ArrayList(T) 的容量，请调用 trimExcess 方法或直接设置 capacity 属性。
	 *           减小容量会重新分配内存并复制 ArrayList(T) 中的所有元素。
	 *           此方法的时间复杂度为O(n)，其中 n 是 count 。
	 */
	public final void clear()
	{
		Array.clear!(T)(theArray);
		theSize = 0;
		theVersion++;
	}
	/**
	 * 从 ArrayList(T) 中移除特定对象的第一个匹配项。
	 * Params: item = 要从 ArrayList(T) 中移除的对象。对于引用类型，该值可以为 null 。
	 * Returns: 如果成功移除 item，则为 true；否则为 false。
	 *          如果在 ArrayList(T) 中没有找到 item，该方法也会返回 false。
	 * Comments: 此方法使用用于 T（列表中的值的类型）的默认相等比较器 DefaultEqualityComparer(T) 来确定相等性。
	 *           此方法执行线性搜索；因此，此方法的运算复杂度为 O(n)，其中 n 是 count。
	 */
	public final bool remove(T item)
	{
		auto index = indexOf(item);
		if( index != -1 )
		{
			removeAt(index);
		}
		return index != -1;
	}
	/**
	 * 确定某元素是否在 ArrayList(T) 中。
	 * Params: item = 要在 ArrayList(T) 中定位的对象。对于引用类型，该值可以为 null 。
	 * Returns: 如果在 ArrayList(T) 中找到 item，则为 true，否则为 false。
	 * Comments: 此方法使用用于 T（列表中的值的类型）的默认相等比较器 DefaultEqualityComparer(T) 来确定相等性。
	 *           此方法执行线性搜索；因此，此方法的运算复杂度为 O(n)，其中 n 是 count。
	 */
	public final bool contains( T item)
	{
		return Array.indexOf!(T)(theArray, item) != -1;
	}

    /* *************************************************************
     * 实现接口IList(T)
     * **************************************************************/

	/**
	 * 获取指定索引处的元素。
	 * Params: index = 要获得的元素从零开始的索引。
	 *         索引值必须小于 count 。
	 * Comments: ArrayList(T) 接受 null 作为引用类型的有效值并且允许有重复的元素。
	 *           通过使用下面的语法，此属性提供了访问集合中特定元素的能力：list[index]。
	 *           检索此属性值的运算复杂度为 O(1)；
	 */
	public final T opIndex(int index)
	in
	{
		assert( index >= 0 && index < this.theSize );
	}
	body
	{
		return theArray[index];
	}
	/**
	 * 设置指定索引处的元素。
	 * Params: index = 要获得的元素从零开始的索引。
	 *         索引值必须小于 count 。
	 *         item = 要设置的元素值。
	 * Comments: ArrayList(T) 接受 null 作为引用类型的有效值并且允许有重复的元素。
	 *           通过使用下面的语法，此属性提供了设置集合中特定元素的能力：list[index] = item。
	 *           设置此属性值的运算复杂度为 O(1)；
	 */
	public final void opIndexAssign(T item, int index)
	in
	{
		assert( index >= 0 && index < this.theSize );
	}
	body
	{
		this.theArray[index] = item;
		this.theVersion++;
	}
	/**
	 * 搜索指定的对象，并返回整个 ArrayList(T) 中第一个匹配项的从零开始的索引。
	 * Params: item = 要在 ArrayList(T) 中定位的对象。对于引用类型，该值可以为 null 。
	 * Returns: 如果在整个 ArrayList(T) 中找到 item 的第一个匹配项，则为该项的从零开始的索引；否则为 -1。
	 * Comments: 从 ArrayList(T) 的第一个元素开始向前搜索，到最后一个元素停止搜索。
	 *			 此方法使用用于 T（列表中的值的类型）的默认相等比较器 DefaultEqualityComparer(T) 来确定相等性。
	 *           此方法执行线性搜索；因此，此方法的运算复杂度为 O(n)，其中 n 是 count。
	 */
	public final int indexOf(T item)
	{
		return Array.indexOf!(T)(theArray[0..theSize], item);
	}
	/**
	 * 搜索指定的对象，并返回 ArrayList(T) 中从指定索引开始并包含指定的元素数的元素范围内第一个匹配项的从零开始的索引。
	 * Params: item = 要在 ArrayList(T) 中定位的对象。对于引用类型，该值可以为 null 。
	 *         index = 从零开始的搜索的起始索引。
	 *         count = 要搜索的部分中的元素数。
	 * Returns: 如果在搜索范围内找到 item 的第一个匹配项，则为该项的从零开始的索引；否则为 -1。
	 * Comments: 如果 count 大于 0，则在 ArrayList(T) 中向前搜索，从 index 处开始，到 index + count - 1 处结束。
	 *           此方法使用用于 T（列表中的值的类型）的默认相等比较器 DefaultEqualityComparer(T) 来确定相等性。
	 *           此方法执行线性搜索；因此，此方法的运算复杂度为 O(n)，其中 n 是 count。
	 */
	public final int indexOf(T item, int index, int count)
	in
	{
		assert( index >= 0 );
		assert( count >= 0 && index + count <= theSize );
	}
	body
	{
		return Array.indexOf(theArray[index..index+count], item);
	}
	/**
	 * 搜索指定的对象，并返回 ArrayList(T) 中从指定索引到最后一个元素的元素范围内第一个匹配项的从零开始的索引。
	 * Params: item = 要在 ArrayList(T) 中定位的对象。对于引用类型，该值可以为 null 。
	 *         index = 从零开始的搜索的起始索引。
	 * Returns: 如果在搜索范围内找到 item 的第一个匹配项，则为该项的从零开始的索引；否则为 -1。
	 * Comments: 如果 count 大于 0，则在 ArrayList(T) 中从 index 开始向前搜索，到最后一个元素停止搜索。
	 *           此方法使用用于 T（列表中的值的类型）的默认相等比较器 DefaultEqualityComparer(T) 来确定相等性。
	 *           此方法执行线性搜索；因此，此方法的运算复杂度为 O(n)，其中 n 是 count。
	 */
	public final int indexOf(T item, int index)
	{
		return indexOf(item, index, theSize-index);
	}
	/**
	 * 将元素插入 ArrayList(T) 的指定索引处。
	 * Params: index = 从零开始的索引，应在该位置插入 item。
	 *         item = 要插入的对象。对于引用类型，该值可以为 null 。
	 * Comments: ArrayList(T) 接受 null 作为引用类型的有效值并且允许有重复的元素。
	 *           如果 count 已经等于 capacity，则在添加新元素之前，
	 *           会通过自动重新分配内部数组来增加 ArrayList(T) 的容量并会将现有元素复制到新数组中。
	 *           如果 index 等于 count，则将 item 添加到 ArrayList(T) 的结尾处。
	 *           此方法的运算复杂度为 O(n)，其中 n 是 count。
	 */
	public final void insert(int index, T item)
	in
	{
		assert( index >= 0 && index <= this.theSize );
	}
	body
	{
		if( theSize == theArray.length )
			needGrow(1);
		//如果索引小于数组内有效内容长度，则把索引位后的所有内容均往后挪一位
		if( index < this.theSize )
			Array.copy!(T)(theArray[index..length], theArray[index+1..length], theSize-index);
		this.theArray[index] = item;
		this.theSize++;
		this.theVersion++;
	}
	/**
	 * 移除 ArrayList(T) 指定索引处的元素。
	 * Params: index = 要移除的元素的从零开始的索引。
	 */
	public final void removeAt(int index)
	in
	{
		assert( index >= 0 && index < this.theSize );
	}
	body
	{
		this.theSize--;
		if( index < this.theSize )
			Array.copy!(T)(theArray[index+1..length], theArray[index..length], theSize-index);
		this.theArray[theSize] = T.init;
		this.theVersion++;
	}

    /* *************************************************************
     * 实现接口IEnumerable(T)
     * *************************************************************/

	/**
	 * 返回循环访问 ArrayList(T) 的枚举数。
	 * Comments: D 语言的 foreach 语句隐藏了枚举数的复杂性。
	 *           因此，建议使用 foreach，而不直接操作枚举数。
	 *           枚举数可用于读取集合中的数据，但不能用于修改基础集合。
	 *
	 *           最初，枚举数定位在集合中第一个元素前。在此位置上，current 属性未定义。
	 *           因此，在读取 current 的值之前，必须调用 moveNext 方法将枚举数提前到集合的第一个元素。
	 *
	 *           在调用 moveNext 之前，current 属性始终返回同一个对象。moveNext 将 current 设置为下一个元素。
	 *
	 *           如果 moveNext 越过集合的结尾，则枚举数将被放置在此集合中最后一个元素的后面，且 moveNext 将返回 false。
	 *           当枚举数位于此位置时，对 moveNext 的后续调用也返回 false。如果对 moveNext 的最近一次调用返回 false，
	 *           则说明没有定义 current。无法再次为集合的第一个元素设置 current；必须改为新建枚举数实例。
	 *
	 *           只要集合保持不变，枚举数就保持有效。如果对集合进行更改（如添加、修改或删除元素），
	 *           则枚举数将失效且不可恢复，而且其行为是不确定的。
	 *
	 *           枚举数没有对集合的独占访问权；因此，从头到尾对一个集合进行枚举在本质上不是一个线程安全的过程。
	 *           若要确保枚举过程中的线程安全，可以在整个枚举过程中锁定集合。
	 *           若要允许多个线程访问集合以进行读写操作，则必须实现自己的同步。
	 *
	 *           system.collections 包中的集合默认实现不同步。
	 *
	 *           此方法的运算复杂度是 O(1)。
	 *
	 */
	public final Enumerator getEnumerator()
	{
		return new Enumerator(this);
	}

	/**
	 * 为 ArrayList(T) 实现 foreach 语句。
	 */
	public final int opApply(int delegate (ref T) dg)
	{
		auto scope enumerator = new Enumerator(this);
        int result = 0;
		while( enumerator.moveNext() )
		{
			auto value = enumerator.current();
			if( (result = dg(value) ) != 0 )
				break;
		}
		return result;
	}

	public final int opApply(int delegate(ref uint, ref T) dg)
	{
		auto scope enumerator = new Enumerator(this);
		int result = 0; 
		uint index = 0;
		while( enumerator.moveNext() )
		{
			auto value = enumerator.current();
			if( (result = dg(index, value)) != 0 )
				break;
			index++;
		}
		return result;
	}

	/**
     * Throws:
     * 		InvalidOperationException，当在遍历对象时修改了集合。
     */
	public final class Enumerator : IEnumerator!(T)
	{
		private ArrayList!(T) theList;
		private int index;
		private int eVersion;

		package this(ArrayList!(T) list)
		{
			theList = list;
			index = -1;
			eVersion = list.theVersion;
		}

		/* *********************************************************
		 * 实现IEnumerator(T)接口
		 * *********************************************************/
		public bool moveNext()
		{
			if(eVersion != theList.theVersion)
				throw new InvalidOperationException(__FILE__ ~"(" ~ __LINE__.stringof ~ ") => " ~ "Collection was modified, enumeration operation can not execute.");
			if( ++index < theList.theSize )
			{
				return true;
			}
			return false;
		}

		public T current()
		{
			if( index == -1 || index == theList.theSize)
				throw new InvalidOperationException(__FILE__ ~"(" ~ __LINE__.stringof ~ ") => " ~ "Enumeration operation can not execute.");
			return theList.theArray[index];
		}

		public void reset()
		{
			if(eVersion != theList.theVersion)
				throw new InvalidOperationException(__FILE__ ~"(" ~ __LINE__.stringof ~ ") => " ~ "Collection was modified, enumeration operation can not execute.");
			index = -1;
		}
	}
	/* *************************************************************
	 * 其他方法
	 * *************************************************************/

	/**
	 * 将集合中的某个元素插入 ArrayList(T) 的指定索引处。
	 * Params: index = 应在此处插入新元素的从零开始的索引。
	 *         collection = 一个集合，应将其元素插入到 ArrayList(T) 中。集合自身不能为 null ，但它可以包含为 null 的元素（如果类型 T 为引用类型）。
	 * Comments: ArrayList(T) 中会保留集合中元素的顺序。
	 *           此方法的运算复杂度为 O(n + m)，其中 n 是要添加的元素数，m 是 count。
	 */
	public final void insertRange(int index, IEnumerable!(T) collection)
	in
	{
		assert(index >= 0 && index <= this.theSize);
		assert(collection !is null);
	}
	body
	{
		auto theCollection = cast(ICollection!(T))collection;
		if(theCollection !is null)
		{
			auto theCount = theCollection.count();
			if( theCount > 0 )
			{
				needGrow(theCount);
				if( index < this.theSize )
				{
					Array.copy!(T)(theArray[index..theSize], theArray[index+theCount..length], theSize-index);
				}
				if( theCollection is this )
				{
					Array.copy!(T)(theArray[0..length], theArray[index..length], index);
					Array.copy!(T)(theArray[(index+count)..length], theArray[cast(int)(index*2)..length], cast(int)(theSize-index));
				}
				else
				{
					T[] array = new T[theCount];
					theCollection.toArray(array);
					Array.copy!(T)(array, theArray[index..length], array.length);
				}
				this.theSize += theCount;
			}
		}
		else
		{
			foreach(i; collection)
			{
				this.insert(index++, i);
			}
		}
		this.theVersion++;
	}
	/**
	 * 将指定集合的元素添加到 ArrayList(T) 的末尾。
	 * Params: collection = 一个集合，应将其元素插入到 ArrayList(T) 中。集合自身不能为 null ，但它可以包含为 null 的元素（如果类型 T 为引用类型）。
	 */
	public final void addRange(IEnumerable!(T) collection)
	{
		this.insertRange(this.theSize, collection);
	}

	/**
	 * 返回当前集合的只读 IList(T) 包装。
	 * Returns: 作为当前 ArrayList(T) 周围的只读包装的 ReadOnlyListCollection(T)。
	 * Comments: 若要防止对 ArrayList(T) 的任何修改，应该仅通过此包装公开 ArrayList(T)。
	 *           只读集合只是一个具有用于防止修改的包装的集合；因此，如果更改基础集合，则只读集合将反映那些更改。
	 *           此方法的运算复杂度是 O(1)。
	 */
	public final ReadOnlyListCollection!(T) asReadOnly()
	{
		return new ReadOnlyListCollection!(T)(this);
	}
	/**
	 * 使用指定的比较器在整个已排序的 ArrayList(T) 中折半搜索元素，并返回该元素从零开始的索引。
	 * Params: item = 要定位的对象。对于引用类型，该值可以为 null。
	 *         comparer = 比较元素时要使用的 IComparer(T) 实现。
	 *         			   或
	 *                     为 null 以使用默认比较器 DefaultComparer(T)。
	 * Returns: 如果找到 item，则为 ArrayList(T) 中的指定 item 的索引。
     *          如果找不到 item，且 item 小于 ArrayList(T) 内任何元素值时，返回 ArrayList(T) 内第一个大于 item 的元素索引值的按位求反值。
	 *          如果找不到 item ，且 item 大于 ArrayList(T) 内任何元素值时，返回 ArrayList(T) 内最后一个元素索引值的按位求反值。
	 *          如果 count 为 0 ，则返回 -1 。
     * Throws: InvalidOperationException, 当 value 没有正确实现 opCmp 时
	 */
	public final int binarySearch(T item, IComparer!(T) comparer = null)
	{
		return Array.binarySearch!(T)(theArray, item, comparer);
	}
	/**
	 * 使用指定的比较器在整个已排序的 ArrayList(T) 指定范围内折半搜索元素，并返回该元素从零开始的索引。
	 * Params: index = 要搜索的范围从零开始的起始索引。
	 *         count = 要搜索的范围的长度。
	 *         item = 要定位的对象。对于引用类型，该值可以为 null。
	 *         comparer = 比较元素时要使用的 IComparer(T) 实现。
	 *         			   或
	 *                     为 null 以使用默认比较器 DefaultComparer(T)。
	 * Returns: 如果找到 item，则为 ArrayList(T) 中的指定 item 的索引。
     *          如果找不到 item，且 item 小于 ArrayList(T) 指定范围内任何元素值时，返回 ArrayList(T) 指定范围内第一个大于 item 的元素索引值的按位求反值。
	 *          如果找不到 item ，且 item 大于 ArrayList(T) 指定范围内任何元素值时，返回 ArrayList(T) 指定范围内最后一个元素索引值的按位求反值。
	 *          如果 count 为 0 ，则返回 -1 。
     * Throws: InvalidOperationException, 当 value 没有正确实现 opCmp 时
	 */
	public final int binarySearch(int index, int count, T item, IComparer!(T) comparer = null)
	in
	{
		assert( index >= 0 );
		assert( count >= 0 );
		assert( index+count <= this.theSize );
	}
	body
	{
		return Array.binarySearch!(T)(theArray[index..index+count], item, comparer);
	}
	/**
	 * 将当前 ArrayList(T) 中的元素转换为另一种类型，并返回包含转换后的元素的列表。
	 * Params: converter = 将每个元素从一种类型转换为另一种类型的委托。
	 * Returns: 目标类型的 ArrayList(T)，其中包含当前 ArrayList(T) 中的转换后的元素。
	 */
	public final ArrayList!(TOutput) convertAll(TOutput)(TOutput delegate(T) converter)
	in
	{
		assert( converter !is null );
	}
	body
	{
		auto list = new ArrayList!(TOutput)(theSize);
		for(auto i = 0; i < theSize; i++)
		{
			list.theArray[i] = converter(this.theArray[i]);
		}
		list.theSize = this.theSize;
		return list;
	}
	///ditto
	public final ArrayList!(TOutput) convertAll(TOutput)(TOutput function(T) converter)
	{
		auto list = new ArrayList!(TOutput)(theSize);
		for(auto i = 0; i < theSize; i++)
		{
			list.theArray[i] = converter(this.theArray[i]);
		}
		list.theSize = this.theSize;
		return list;
	}
	/**
	 * 搜索与指定谓词所定义的条件相匹配的一个元素，
	 * 并返回 ArrayList(T) 中从指定的元素范围内第一个匹配项的从零开始的索引。
	 * Params: startIndex = 从零开始的搜索的起始索引。
	 *         count = 要搜索的部分中的元素数。
	 *         match = 用于定义要搜索的元素的条件。
	 * Returns: 如果找到与 match 定义的条件相匹配的第一个元素，则为该元素的从零开始的索引；否则为 -1。
	 */
	public final int findIndex(int startIndex, int count, bool delegate(T) match)
	in
	{
		assert( startIndex >= 0 && startIndex < theSize );
		assert( count >= 0 && (theSize - count) >= startIndex );
		assert( match !is null );
	}
	body
	{
		auto highIndex = startIndex+count;
		for(auto i = 0; i < highIndex; i++)
		{
			if(match(this.theArray[i]))
				return i;
		}
		return -1;
	}
	///ditto
	public final int findIndex(int startIndex, int count, bool function(T) match)
	in
	{
		assert( startIndex >= 0 && startIndex < theSize );
		assert( count >= 0 && (theSize - count) >= startIndex );
		assert( match !is null );
	}
	body
	{
		auto highIndex = startIndex+count;
		for(auto i = 0; i < highIndex; i++)
		{
			if(match(this.theArray[i]))
				return i;
		}
		return -1;
	}
	///ditto
	public final int findIndex(int startIndex, bool delegate(T) match)
	{
		return findIndex(startIndex, this.theSize-startIndex, match);
	}
	///ditto
	public final int findIndex(int startIndex, bool function(T) match)
	{
		return findIndex(startIndex, this.theSize-startIndex, match);
	}
	///ditto
	public final int findIndex(bool delegate(T) match)
	{
		return findIndex(0, this.theSize, match);
	}
	///ditto
	public final int findIndex(bool function(T) match)
	{
		return findIndex(0, this.theSize, match);
	}
	/**
	 * 确定 ArrayList(T) 是否包含与指定谓词所定义的条件相匹配的元素。
	 */
	public final bool exists(bool delegate(T) match)
	{
		return findIndex(match) != -1;
	}
	///ditto
	public final bool exists(bool function(T) match)
	{
		return findIndex(match) != -1;
	}
	/**
	 * 搜索与指定谓词所定义的条件相匹配的元素，并返回整个 ArrayList(T) 中的第一个匹配元素。
	 */
	public final T find(bool delegate(T) match)
	in
	{
		assert( match !is null );
	}
	body
	{
		for(auto i = 0; i < theSize; i++)
		{
			if(match(theArray[i]))
				return theArray[i];
		}
		return T.init;
	}
	///ditto
	public final T find(bool function(T) match)
	in
	{
		assert( match !is null );
	}
	body
	{
		for(auto i = 0; i < theSize; i++)
		{
			if(match(theArray[i]))
				return theArray[i];
		}
		return T.init;
	}
	/**
	 * 检索与指定谓词定义的条件匹配的所有元素。
	 * Params: match = 用于定义要搜索的元素应满足的条件。
	 * Returns: 如果找到，则为一个 ArrayList(T)，其中包含与指定谓词所定义的条件相匹配的所有元素；
	 *          否则为一个空 ArrayList(T)。
	 */
	public final ArrayList!(T) findAll(bool delegate(T) match)
	in
	{
		assert( match !is null );
	}
	body
	{
		auto list = new ArrayList!(T)();
		for(auto i=0; i<theSize; i++)
		{
			if(match(theArray[i]))
				list.add(theArray[i]);
		}
		return list;
	}
	///ditto
	public final ArrayList!(T) findAll(bool function(T) match)
	in
	{
		assert( match !is null );
	}
	body
	{
		auto list = new ArrayList!(T)();
		for(auto i=0; i<theSize; i++)
		{
			if(match(theArray[i]))
				list.add(theArray[i]);
		}
		return list;
	}
	/**
	 * 搜索与指定谓词所定义的条件相匹配的元素，并返回整个 ArrayList(T) 中的最后一个匹配元素。
	 * Returns: 如果找到，则为与指定谓词所定义的条件相匹配的最后一个元素；否则为类型 T 的默认值。
	 * Comments: <b>重要说明:</b>
	 *           当搜索包含值类型的列表时，请确保该类型的默认值不满足搜索谓词。
	 *           否则，将无法区分是默认值指示没有找到匹配项，还是刚巧有一个列表元素具有该类型的默认值。
	 *           如果默认值满足搜索谓词，请改用 findLastIndex 方法。
	 */
	public final T findLast(bool delegate(T) match)
	in
	{
		assert( match !is null );
	}
	body
	{
		for( auto i = theSize-1; i >= 0; i-- )
		{
			if(match(theArray[i]))
				return theArray[i];
		}
		return T.init;
	}
	///ditto
	public final T findLast(bool function(T) match)
	in
	{
		assert( match !is null );
	}
	body
	{
		for( auto i = theSize-1; i >= 0; i-- )
		{
			if(match(theArray[i]))
				return theArray[i];
		}
		return T.init;
	}
	/**
	 * 搜索与指定谓词所定义的条件相匹配的元素，并返回 ArrayListList(T) 中指定元素范围内最后一个匹配项的从零开始的索引。
	 * Params: startIndex = 向后搜索的从零开始的起始索引。
	 *         count = 要搜索的部分中的元素数。
	 *         match = 用于定义要搜索的元素的条件。
	 * Returns: 如果找到与 match 定义的条件相匹配的最后一个元素，则为该元素的从零开始的索引；否则为 -1。
	 */
	public final int findLastIndex(int startIndex, int count, bool delegate(T) match)
	in
	{
		assert( startIndex >= 0 && startIndex < theSize );
		assert( count >= 0 && (startIndex - count + 1) >= 0 );
		assert( match !is null );
	}
	body
	{
		auto index = startIndex - count;
		for( auto i = startIndex; i > index; i-- )
		{
			if(match(theArray[i]))
				return i;
		}
		return -1;
	}
	///ditto
	public final int findLastIndex(int startIndex, int count, bool function(T) match)
	in
	{
		assert( startIndex >= 0 && startIndex < theSize );
		assert( count >= 0 && (startIndex - count + 1) >= 0 );
		assert( match !is null );
	}
	body
	{
		auto index = startIndex - count;
		for( auto i = startIndex; i > index; i-- )
		{
			if(match(theArray[i]))
				return i;
		}
		return -1;
	}
	///ditto
	public final int findLastIndex(int startIndex, bool delegate(T) match)
	{
		return findLastIndex(startIndex, startIndex+1, match);
	}
	///ditto
	public final int findLastIndex(int startIndex, bool function(T) match)
	{
		return findLastIndex(startIndex, startIndex+1, match);
	}
	///ditto
	public final int findLastIndex(bool delegate(T) match)
	{
		return findLastIndex(theSize-1, theSize, match);
	}
	///ditto
	public final int findLastIndex(bool function(T) match)
	{
		return findLastIndex(theSize-1, theSize, match);
	}
	/**
	 * 对 ArrayList(T) 的每个元素执行指定操作。
	 */
	public final void forEach(void delegate(T) action)
	in
	{
		assert( action !is null );
	}
	body
	{
		for(auto i = 0; i < theSize; i++)
		{
			action(theArray[i]);
		}
	}
	///ditto
	public final void forEach(void function(T) action)
	in
	{
		assert( action !is null );
	}
	body
	{
		for(auto i = 0; i < theSize; i++)
		{
			action(theArray[i]);
		}
	}
	/**
	 * 创建源 ArrayList(T) 中的元素范围的浅拷贝副本。
	 * Params: index = 从零开始的 ArrayList(T) 起始索引。
	 *         count = 要拷贝的元素数。
	 * Comments: 引用类型的集合或该集合的子集的浅拷贝副本仅包含对该集合的元素的引用。
	 *           对象本身并未被复制。
	 *           新列表中的引用与原始列表中的引用指向相同的对象。
	 *
	 *           值类型的集合或该集合的子集的浅拷贝副本包含该集合的元素。
	 *           但是，如果该集合的元素包含对其他对象的引用，则这些对象不会被复制。
	 *           新集合中的元素中的引用与原始集合中的元素的引用指向相同的对象。
	 *
	 *           与之相对，集合的深拷贝将复制这些元素以及由它们直接或间接引用的所有内容。
	 *
	 *           此方法的运算复杂度为 O(n)，其中 n 是 count。
	 */
	public final ArrayList!(T) getRange(int index, int count)
	in
	{
		assert( index >= 0 );
		assert( count >= 0 && (index+count) <= theSize );
	}
	body
	{
		auto list = new ArrayList!(T)(count);
		list.theArray = this.theArray[index..index+count].dup;
		list.theSize = count;
		return list;
	}
	/**
	 * 搜索指定的对象，并返回 ArrayList(T) 指定的元素范围内最后一个匹配项的从零开始的索引。
	 * Params: item = 要在 ArrayList(T) 中定位的对象。对于引用类型，该值可以为 null。
	 *         index = 向后搜索的从零开始的起始索引。
	 *         count = 要搜索的指定范围内的元素数。
	 * Returns: 如果在 ArrayListList(T) 指定的元素范围内找到 item 的最后一个匹配项，则为该项的从零开始的索引；
	 *          否则为 -1。
	 */
	public final int lastIndexOf(T item, int index, int count)
	in
	{
		assert( index >= 0 );
		assert( count >= 0 );
		assert( (index - count + 1) >= 0 );
	}
	body
	{
		auto startIndex = index - count;
		return Array.lastIndexOf(theArray[startIndex..index], item);
	}
	///ditto
	public final int lastIndexOf(T item, int index)
	{
		return lastIndexOf(item, index, index+1);
	}
	///ditto
	public final int lastIndexOf(T item)
	{
		return lastIndexOf(item, theSize-1, theSize);
	}
	/**
	 * 移除与指定的谓词所定义的条件相匹配的所有元素。
	 * Params: match = 用于定义要移除的元素应满足的条件。
	 * Returns: 从 ArrayList(T) 中移除的元素数目。
	 */
	public final int removeAll(bool delegate(T) match)
	in
	{
		assert( match !is null );
	}
	body
	{
		int i = 0;
		int j = 0;
		// Find the first item to remove
		for (i = 0; i < theSize; i++)
		{
			if (match(theArray[i]))
				break;
		}

		if (i == theSize)
			return 0;

		// Remove any additional items
		for (j = i + 1; j < theSize; j++)
		{
			if (!match(theArray[j]))
				theArray[i++] = theArray[j];
		}
		Array.clear!(T)(theArray[i..j]);
		theSize = i;
		theVersion++;
		return (j - i);
	}

	/**
	 * 移除与指定的谓词所定义的条件相匹配的所有元素。
	 * Params: match = 用于定义要移除的元素应满足的条件。
	 * Returns: 从 ArrayList(T) 中移除的元素数目。
	 */
	public final int removeAll(bool function(T) match)
	in
	{
		assert( match !is null );
	}
	body
	{
		int i = 0;
		int j = 0;
		// Find the first item to remove
		for (i = 0; i < theSize; i++)
		{
			if (match(theArray[i]))
				break;
		}

		if (i == theSize)
			return 0;

		// Remove any additional items
		for (j = i + 1; j < theSize; j++)
		{
			if (!match(theArray[j]))
				theArray[i++] = theArray[j];
		}
		Array.clear!(T)(theArray[i..j]);
		theSize = i;
		theVersion++;
		return (j - i);
	}

	/**
	 * 从 ArrayList(T) 中移除一定范围的元素。
	 * Params: index = 要移除的元素的范围从零开始的起始索引。
	 *         count = 要移除的元素数。
	 * Comments: 项被移除，ArrayList(T) 中在这些项之后的所有元素的索引都减小 count。
	 */
	public final void removeRange(int index, int count)
	in
	{
		assert( index >= 0 );
		assert( count >= 0 );
		assert( index + count <= theSize );
	}
	body
	{
		if( count > 0 )
		{
			theSize -= count;
			if( index < theSize )
			{
				Array.copy!(T)(theArray[index+count..length], theArray[index..length], theSize-index);
			}
			Array.clear!(T)(theArray[theSize..theSize+count]);
			theVersion++;
		}
	}
	/**
	 * 将 ArrayList(T) 指定范围内元素的顺序反转。
	 */
	public final void reverse(int index, int count)
	in
	{
		assert( index >= 0 );
		assert( count >= 0 );
		assert( index + count <= theSize );
	}
	body
	{
		theArray[index..index+count].reverse;
		theVersion++;
	}
	///ditto
	public final void reverse()
	{
		this.reverse(0, theSize);
	}
	/**
	 * 使用指定的比较器对 ArrayList(T) 中某个范围内的元素进行排序。
	 * Params: index = 要排序的范围的从零开始的起始索引。
	 *         count = 要排序的范围的长度。
	 *         comparer = 比较元素时要使用的 IComparer(T) 实现，或者为 null，表示使用默认比较器 DefaultComparer(T)。
	 */
	public final void sort(int index, int count, IComparer!(T) comparer = null)
	in
	{
		assert( index >= 0 );
		assert( count >= 0 );
		assert( index + count <= theSize );
	}
	body
	{
		Array.sort!(T)(theArray[index..index+count], comparer);
		theVersion++;
	}
	///ditto
	public final void sort(IComparer!(T) comparer)
	{
		Array.sort!(T)(theArray[0..theSize], comparer);
	}
	///ditto
	public final void sort()
	{
		Array.sort!(T)(theArray[0..theSize]);
	}
	/**
	 * 使用指定的比较委托对整个 ArrayList(T) 的元素进行排序。
	 */
	public final void sort(int delegate(T, T) comparison)
	in
	{
		assert( comparison !is null );
	}
	body
	{
		Array.sort!(T)(theArray[0..theSize], comparison);
		theVersion++;
	}
	///ditto
	public final void sort(int function(T, T) comparison)
	in
	{
		assert( comparison !is null );
	}
	body
	{
		Array.sort!(T)(theArray[0..theSize], comparison);
		theVersion++;
	}
	/**
	 * 将容量设置为 ArrayList(T) 中的实际元素数目（如果该数目小于某个阈值）。
	 * Comments: 如果不向集合中添加新元素，则此方法可用于最小化集合的内存开销。
	 *           但是，重新分配和复制很大的 ArrayList(T) 的开销可能很大，
	 *           因此，如果列表大于容量的 90%，则 trimExcess 方法将不执行任何操作。
	 *           这样可以避免为获得相对较少的收益而产生大量重新分配开销。
	 */
	public final void trimExcess()
	{
		auto threshold = cast(int)(theArray.length * 0.9);
		if( theSize < threshold )
		{
			this.capacity = theSize;
		}
	}
	/**
	 * 确定是否 ArrayList(T) 中的每个元素都与指定的谓词所定义的条件相匹配。
	 * Params: match = 定义要据以检查元素的条件。
	 * Returns: 如果 ArrayList(T) 中的每个元素都与指定的谓词所定义的条件相匹配，则为 true；否则为 false。
	 *          如果列表不包含任何元素，则返回值为 true。
	 */
	public final bool trueForAll(bool delegate(T) match)
	in
	{
		assert( match !is null );
	}
	body
	{
		for(auto i = 0; i < theSize; i++)
		{
			if(!match(theArray[i]))
				return false;
		}
		return true;
	}
	///ditto
	public final bool trueForAll(bool function(T) match)
	in
	{
		assert( match !is null );
	}
	body
	{
		for(auto i = 0; i < theSize; i++)
		{
			if(!match(theArray[i]))
				return false;
		}
		return true;
	}
}

unittest
{
	//注意：这个单元测试不但测试了 ArrayList(T)，同时也间接测试了Array类的方法

	//测试insert()
	auto stringList = new ArrayList!(string)();
	with(stringList)
	{
		insert(0, "a");
		insert(0, "b");
		insert(1, "c");
	}

	assert( stringList.count == 3 );
	assert( stringList[0] == "b" );
	assert( stringList[1] == "c" );
	assert( stringList[2] == "a" );

	auto array = [55,50,22,80,56,52,40,63];
	auto list = new ArrayList!(int)(8);
	foreach( i; array )
	{
		list.add(i);
	}
	//测试insertRange()
	auto count = list.count;
	auto newArray = [1,2,3];
	auto newRange = new ArrayList!(int)(3);
	foreach(i; newArray)
	{
		newRange.add(i);
	}

	list.insertRange(1, newRange);

	assert( count+3 == list.count );
	assert( list[0] == 55 );
	assert( list[1] == 1 );
	assert( list[2] == 2 );
	assert( list[3] == 3 );
	assert( list[4] == 50 );

	newRange = new ArrayList!(int)();
	auto newList = new ArrayList!(int)();
	newList.add(1);
	newRange.insertRange(0, newList);
	newRange.insertRange(newRange.count, newList);
	assert(newRange.count == 2);

	//测试insertRange() - 插入自己
	newRange = new ArrayList!(int)(5);
	for(auto i = 0; i < 5; i++)
	{
		newRange.add(i);
	}
	newRange.insertRange(2, newRange);

	assert(newRange.count == 10);
	assert(newRange[0] == 0);
	assert(newRange[1] == 1);
	assert(newRange[2] == 0);
	assert(newRange[3] == 1);
	assert(newRange[4] == 2);
	assert(newRange[5] == 3);
	assert(newRange[6] == 4);
	assert(newRange[7] == 2);
	assert(newRange[8] == 3);
	assert(newRange[9] == 4);

	//测试indexOf()
	newList = new ArrayList!(int)();
	newList.add(100);
	newList.add(200);

	assert( newList.indexOf(200) == 1 );

	try
	{
		newList.indexOf(0, 0, 10);
	}
	catch(Error e)
	{
		assert(true);
	}

	//测试getRange()
	newList = list.getRange(2,4);

	assert( newList.count == 4 );
	assert( newList[0] == 2 );
	assert( newList[1] == 3 );
	assert( newList[2] == 50 );
	assert( newList[3] == 22 );

	//测试迭代器
	auto enumerator = list.getEnumerator();

	try
	{
		enumerator.current();
	}
	catch(InvalidOperationException e)
	{
		assert(true);
	}

	auto listContent = [55,1,2,3,50,22,80,56,52,40,63];

	for(auto i = 0; i < list.count; i++)
	{
		assert( enumerator.moveNext() );
		assert( listContent[i] == enumerator.current );
	}

	assert( !enumerator.moveNext() );

	try
	{
		enumerator.current();
	}
	catch(InvalidOperationException e)
	{
		assert(true);
	}

	foreach( i, j; list )
	{
		assert( listContent[i] == j );
	}

	//测试构造函数
	auto objectListA = new ArrayList!(Object)(1);
	auto objectListB = new ArrayList!(Object)(50);
	auto objectListC = new ArrayList!(Object)(0);

	assert( objectListA.capacity == 1 );
	assert( objectListB.capacity == 50 );
	assert( objectListC.capacity == 0 );

	try
	{
		newList = new ArrayList!(int)(-1);
	}
	catch(Error e)
	{
		assert(true);
	}

	newList = new ArrayList!(int)(list);

	assert( newList.count == list.count );
	for(auto i = 0; i < newList.count; i++)
	{
		assert( newList[i] == list[i] );
	}

	try
	{
		newList = new ArrayList!(int)(null);
	}
	catch(Error e)
	{
		assert(true);
	}

	//测试add()
	auto numbers = list.count;
	list.add(-1);

	assert( numbers+1 == list.count );
	assert( list[list.count-1] == -1 );

	//测试addRange()
	numbers = list.count;
	auto range = [-1,-2,-3];
	newRange = new ArrayList!(int)(3);
	foreach(i; range)
	{
		newRange.add(i);
	}
	list.addRange(newRange);

	assert( numbers+3 == list.count );
	assert( list[list.count-3] == -1 );
	assert( list[list.count-2] == -2 );
	assert( list[list.count-1] == -3 );

	try
	{
		list.addRange(null);
	}
	catch(Error e)
	{
		assert(true);
	}

	//测试binarySearch()
	newList = new ArrayList!(int)(list);

	newList.sort();

	assert(newList.binarySearch(1) == 4);
	assert(newList.binarySearch(-3) == 0);
	assert(newList.binarySearch(23) < 0);
	assert(newList.binarySearch(100) == ~(newList.count-1));
	assert(newList.binarySearch(23) == ~(newList.binarySearch(22)+1));
	assert(newList.binarySearch(-4) == ~0);

	newList.clear();
	assert(newList.binarySearch(-1) == -1);

	//测试sort()
	newList = new ArrayList!(int)(list);

	newList.sort();

	for(auto i = 0; i < newList.count-1; i++)
	{
		assert( newList[i] <= newList[i+1] );
	}

	//测试clear()
	newList = new ArrayList!(int)(list);
	auto capacity = newList.capacity;
	newList.clear();
	assert( newList.count == 0 );
	assert( capacity == newList.capacity );

	//测试contains()
	assert( list.contains(22) );
	assert( !list.contains(23) );

	//测试convertAll()
	stringList = list.convertAll!(string)(delegate string(int i){return "50";});

	assert( stringList.count == list.count );
	assert( stringList[0] == "50" );
	assert( stringList[1] == "50" );
	assert( stringList[2] == "50" );

	//测试toArray()
	auto intArray = new int[2];
	list.toArray(intArray[0..2]);

	assert( intArray[0] == 55 );
	assert( intArray[1] == 1 );

	try
	{
		list.toArray(null);
	}
	catch(Error e)
	{
		assert(true);
	}

	//测试find()
	assert( list.find(delegate bool(int i) {return i % 3 == 0;}) == 3 );
	assert( list.find(function bool(int i) {return i % 3 == 0;}) == 3 );

	try
	{
		list.find(cast(bool delegate(int))null);
	}
	catch(Error e)
	{
		assert(true);
	}

	//测试findAll()
	auto result = list.findAll(delegate bool(int i) {return i % 4 == 0;});
	assert( result.count == 4 );
	assert( result[0] == 80 );
	assert( result[1] == 56 );
	assert( result[2] == 52 );
	assert( result[3] == 40 );

	//测试小数组findAll()
	result = list.findAll(delegate bool(int i) {return i % 12 == 0;});
	assert( result !is null );
	assert( result.count == 0 );

	newList = new ArrayList!(int)(10000);
	for(auto i = 1; i <= 10000; i++)
	{
		newList.add(i);
	}

	result = newList.findAll(delegate bool(int i) {return i % 4 == 0;});
	assert( result.count == 2500 );

	result = newList.findAll(delegate bool(int i) {return i % 12 == 0;});
	assert( result.count == 833 );

	//测试大数组findAll()
	newList = new ArrayList!(int)(70000);
	for(auto i = 1; i <= 80000; i++)
	{
		newList.add(i);
	}
	result = newList.findAll(delegate bool(int i) {return i % 4 == 0;});
	assert( result.count == 20000 );

	result = newList.findAll(delegate bool(int i) {return i % 12 == 0;});
	assert( result.count == 6666 );

	try
	{
		newList.findAll(cast(bool delegate(int))null);
	}
	catch(Error e)
	{
		assert(true);
	}

	//测试findIndex()
	assert(list.findIndex(delegate bool(int i) {return i % 3 == 0;}) == 3);
	assert(list.findIndex(delegate bool(int i) {return i % 12 == 0;}) == -1);

	try
	{
		newList.findIndex(cast(bool delegate(int))null);
	}
	catch(Error e)
	{
		assert(true);
	}

	//测试findLast()
	assert(list.findLast(delegate bool(int i) {return i % 4 == 0;}) == 40);

	//测试findLastIndex()
	assert(list.findLastIndex(delegate bool(int i) {return i % 4 == 0;}) == 9);
	assert(list.findLastIndex(5, delegate bool(int i) {return i % 4 == 0;}) == -1 );

	try
	{
		newList.findLastIndex(cast(bool delegate(int))null);
	}
	catch(Error e)
	{
		assert(true);
	}

	//测试remove()
	numbers = list.count;
	assert( list.remove(22) );
	assert( list.count == numbers-1 );
	assert( list.indexOf(22) == -1 );
	assert( !list.remove(0) );

	//测试removeAll()
	numbers = list.count;
	auto removedCount = list.removeAll(delegate bool(int i) {return i % 4 == 0;});
	assert( removedCount == 4 );
	assert( list.count == numbers-4 );

	removedCount = list.removeAll(delegate bool(int i) {return i % 12 == 0;});
	assert( removedCount == 0 );

	//测试removeAt()
	numbers = list.count;
	list.removeAt(0);
	assert( list[0] == 1 );
	assert( list.count == numbers-1 );

	//测试removeRange()
	numbers = list.count;
	list.removeRange(1, 2);
	assert( list.count == numbers-2 );
	assert( list[0] == 1 );
	assert( list[1] == 50 );

	newList = new ArrayList!(int)();
	list.removeRange(0, 0);

	try
	{
		list.removeRange(1, list.count);
	}
	catch(Error e)
	{
		assert(true);
	}

	//测试reverse()
	numbers = list.count;
	list.reverse();
	//[-3,-2,-1,-1,63,50,1]
	assert( list.count == numbers );
	assert( list[0] == -3 );
	assert( list[list.count-1] == 1 );

	list.reverse(0, 2);
	//[-2, -3, -1, -1, 63, 50, 1]
	assert(list[0] == -2);
	assert(list[1] == -3);

	try
	{
		list.reverse(1, list.count);
	}
	catch(Error e)
	{
		assert(true);
	}

	//测试trimExcess()
	stringList = new ArrayList!(string)();
	stringList.add("foo");

	assert( stringList.count < stringList.capacity );
	stringList.trimExcess();
	assert( stringList.count == stringList.capacity );

	//测试trueForAll()
	assert( !list.trueForAll(delegate bool(int i){return i % 4 == 0;}) );
	assert( list.trueForAll(function bool(int i){return i > -4;}) );

	//测试capacity
	try
	{
		list.capacity = list.count - 1;
	}
	catch(Error e)
	{
		assert(true);
	}

	//测试在迭代时修改容器元素值是否引发异常
	newList = new ArrayList!(int)();
	enumerator = newList.getEnumerator();
	newList.add(5);
	try
	{
		enumerator.moveNext();
	}
	catch(InvalidOperationException e)
	{
		assert(true);
	}

	newList = new ArrayList!(int)();
	enumerator = newList.getEnumerator();
	newList.addRange(list);
	try
	{
		enumerator.moveNext();
	}
	catch(InvalidOperationException e)
	{
		assert(true);
	}

	newList = new ArrayList!(int)();
	enumerator = newList.getEnumerator();
	newList.clear();
	try
	{
		enumerator.moveNext();
	}
	catch(InvalidOperationException e)
	{
		assert(true);
	}

	newList = new ArrayList!(int)();
	enumerator = newList.getEnumerator();
	newList.insert(0,4);
	try
	{
		enumerator.moveNext();
	}
	catch(InvalidOperationException e)
	{
		assert(true);
	}

	newList = new ArrayList!(int)();
	enumerator = newList.getEnumerator();
	newList.insertRange(0, list);
	try
	{
		enumerator.moveNext();
	}
	catch(InvalidOperationException e)
	{
		assert(true);
	}

	newList = new ArrayList!(int)();
	newList.add(5);
	enumerator = newList.getEnumerator();
	newList.remove(5);
	try
	{
		enumerator.moveNext();
	}
	catch(InvalidOperationException e)
	{
		assert(true);
	}
	enumerator = newList.getEnumerator();
	newList.remove(7);
	enumerator.moveNext();

	newList = new ArrayList!(int)();
	newList.addRange(list);
	enumerator = newList.getEnumerator();
	newList.removeRange(0,list.count);
	try
	{
		enumerator.moveNext();
	}
	catch(InvalidOperationException e)
	{
		assert(true);
	}

	newList = new ArrayList!(int)();
	newList.add(5);
	enumerator = newList.getEnumerator();
	newList.removeAt(0);
	try
	{
		enumerator.moveNext();
	}
	catch(InvalidOperationException e)
	{
		assert(true);
	}

	newList = new ArrayList!(int)();
	newList.add(4);
	enumerator = newList.getEnumerator();
	newList.removeAll(delegate bool(int i){return i % 4 == 0;});
	try
	{
		enumerator.moveNext();
	}
	catch(InvalidOperationException e)
	{
		assert(true);
	}

	newList = new ArrayList!(int)();
	newList.add(1);
	newList.add(2);
	newList.add(3);
	try
	{
        foreach(item; newList)
        {
            newList.add(4);
        }
	}
	catch(InvalidOperationException e)
	{
	    assert(true);
	}
}